package com.leetcode.动态规划.买卖股票的最佳时机;

/**
 * 给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * 
 */ 
public class L309最佳买卖股票时机含冷冻期 {
	public static void main(String[] args) {
		int result = maxProfit(new int[] {1,2,3,0,2});
		System.out.println(result);
	}
	
	/**
	 * 定义4个状态：
	 * j=0,状态一：今日持有股票（前一天就有股票，或是前一天是冷冻期，或是前一天保持卖出股票状态（状态二））
	 * j=1,状态二：前两天卖出股票（前一天保持卖出股票状态，或前一天是冷冻期）
	 * j=2,状态三：今日卖出股票（只有一种情况）
	 * j=3,状态四：今日是冷冻期
	 * dp[i][j]:第i天对应状态j所得的最大现金
	 * 则 dp[i][0] = max(dp[i - 1][0],dp[i - 1][3] - prices[i],dp[i - 1][1] - prices[i])
	 * dp[i][1] = max(dp[i - 1][1],dp[i - 1][3])
	 * dp[i][2] = dp[i - 1][0] + prices[i]
	 * dp[i][3] = dp[i - 1][2]
	 * 初始化：
	 * dp[0][0]=-prices[0]//根据定义，只能是当日买入
	 * dp[0][1]=0//首日并没有股票可以卖出，最高收入为0
	 * dp[0][2]=0//首日并没有股票可以卖出，最高收入为0
	 * dp[0][3]=0//首日并没有股票可以卖出，最高收入为0
	 * @param prices
	 * @return
	 */
	public static int maxProfit(int[] prices) {
		int n = prices.length;
		if(n == 0) return 0;
		int[][] dp = new int[n][4];
		dp[0][0] = -prices[0];
		for(int i = 1;i < n;i++) {
			dp[i][0] = Math.max(dp[i - 1][0],Math.max(dp[i - 1][3] - prices[i],dp[i - 1][1] - prices[i]));
			dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][3]);
			dp[i][2] = dp[i - 1][0] + prices[i];
			dp[i][3] = dp[i - 1][2];
		}
		return Math.max(dp[n - 1][1],Math.max(dp[n - 1][2],dp[n - 1][3]));
	}
}
